Modem packet switching networks are used to carry a variety of different types of information for a wide variety of users and applications. As the use of packet based networks and the diversity of applications to be supported is increasing, support for advanced networking services such as Service Level Agreement (“SLA”) monitoring, traffic engineering, security, billing and the like, to name a few, is becoming a requirement.
One technique for implementing these advanced network services is to classify packets transported within the network into flows and assign actions to be taken on the packets based on the flow assignment. Based on the flow assignment, the network may ensure all packets of this flow receive the appropriate priority and reserve the necessary bandwidth along the path to the destination. The criteria for classification into flows may be diverse; it may include information from the header of a packet, some part of the packet payload or other information such as the ingress or egress interface associated with the packet. This criteria for classification is specified in the form of classification rules. Any packet matching the criteria specified in a classification rule will be classified into the same flow.
In conventional network processor unit (“NPU”), the diverse set of classification rules may be stored in a number of lookup tables. These lookup tables are indexed into by the classification engine to determine the flow to which an incoming packet should be assigned. Since packet classification is executed in real-time at line rates, these lookup tables are often maintained in expensive, high speed, low latency memory (e.g., SRAM), which is a finite and valuable resource.
Lookup tables may also be used to implement other functionality within a NPU, such as Internet Protocol (“IP”) forwarding to route a packet from its source to its destination. EP forwarding is a layer three operation that uses IP addresses to make forwarding decisions. The NPU indexes into a routing table stored in a lookup table using the destination IP address within the packet (or datagram) as the index key. The IP forwarding decision chooses the next hop IP address as well as an output port of the router through which the next hop may be reached. Conceptually, a routing table contains an entry for each possible destination along with a next hop used to reach the destination.
Conventional lookup tables are established by pre-allocating a contiguous block of memory and populating the memory with entries of the lookup table. The amount of memory pre-allocated is generally determined based on an estimate of the maximum foreseeable number of entries. Even if only a fraction of the maximum number of entries is actually used, the entire block of pre-allocated memory remains reserved, resulting in wasteful consumption of a valuable resource.
Since each lookup table in an NPU may be designed for a unique purpose (e.g., classification, IP forwarding, database access, etc.), each lookup table can have a unique format and its own set of management/access functions (also referred to as application program interfaces (“APIs”)) developed by the table designer. Although the various APIs for the lookup tables may execute the same or similar table functions, each lookup table has its own set of APIs due to non-unified formats of the various lookup tables. These redundant APIs are stored in memory and consume valuable memory resources, as well.